2912. SPRIME - Super Primes

In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself.

Super-prime numbers are the elements of the subsequence of prime-numbers that occupy prime-numbered positions within the sequence of all prime numbers. That is, if p(i) denotes the ith prime number, the numbers in this sequence are those of the form p(p(i)) or Primes with a prime index in the sequence of prime numbers (the 2nd, 3rd, 5th, ... prime).

Your task is to generate all super primes < 10⁷.

Input.

There is NO input for this problem.

Output. Print all super-primes < 10⁷ in ascending order, one per line.

Sample Output – first few lines

3

5

11

17

31

41

59

...

РЕШЕНИЕ

решето Эратосфена

Анализ алгоритма

Сгенерируем решето Эратосфена для чисел от 1 до 10⁷. Перенумеруем простые числа. Далее выведем такие простые числа, номера которых являются простыми. Первым простым числом согласно условия задачи является 2.

Пример

Перенумеруем простые числа: первым простым числом является 2, вторым простым 3, третьим простым 5 и так далее.

Простыми числами, находящимися на простых позициях (2, 3, 5, 7, 11, …), будут 3, 5, 11, 17, 31, … .

Реализация алгоритма

#include <stdio.h>

#include <math.h>

#define MAX 10000001

char primes[MAX];

int i, c;

void gen_primes(void)

{

int i, j;

for(i = 0; i < MAX; i++) primes[i] = 1;

for(i = 2; i <= (int)sqrt(1.0*MAX); i++)

if (primes[i])

for(j = i * i; j < MAX; j += i) primes[j] = 0;

}

int main(void)

{

gen_primes();

c = 1;

for(i = 3; i < MAX; i++)

if (primes[i])

{

c++;

if (primes[c]) printf("%d\n",i);

}

return 0;

}